package tree_map_set;

/**
 *  二叉搜索树:二叉搜索树中不能有重复数据
 */
public class BinarySearchTree {

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root; //根节点


    /**
     * 查找 key 是否在二叉搜索树中
     *
     * @param key 需要查找的值
     * @return 找到返回该节点，找不到返回 null
     */
    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    /**
     *  普通二叉搜索树的插入：插入已有的数据是插入不成功的
     *  既是插入，也是构建二叉搜索树
     */
    public boolean insert(int key) {

        TreeNode newNode = new TreeNode(key);
        if(root == null) {
            root = newNode;
            return true;
        }

        TreeNode prev = null; //cur 的前驱
        TreeNode cur = root;
        while(cur != null) {
            prev = cur;
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return false;
            }
        }
        //assert prev != null;
        if(prev.val > key) {
            prev.left = newNode;
        }else {
            prev.right = newNode;
        }
        return true;
    }

    /**
     *  难点：01：15：00 左右
     *  普通二叉搜索树的删除
     */
    public void remove(int key) {
        if(root == null) { return; }

        TreeNode parent = null; //cur的父亲节点
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //找到了 开始删除
                removeNode(cur,parent);
                return;
            }
        }
    }

    /**
     * 进行删除,需要分类讨论
     * @param cur 当前需要删除的节点
     * @param parent  节点cur 的父亲节点
     */
    private void removeNode(TreeNode cur, TreeNode parent) {
        //走到这 root 就不会为空

        if(cur.left == null) { //大前提1：cur.left == null !!!

            //1.cur 是根节点,则root = cur.right
            if(cur == root) { root = cur.right; }

            //2.cur 不是root,是parent.left -》 则parent.left = cur.right
                //这是因为cur的左孩子为空,cur只有右孩子,因此parent.left只需等于cur.right即可
            if(cur == parent.left) { parent.left = cur.right; }

            //3.cur 不是root,是parent.right -》 则parent.left = cur.right
            if(cur == parent.right) { parent.right = cur.right; }

        }else if(cur.right == null){ //大前提2：cur.right == null !!!

            //1.cur 是根节点,则root = cur.left
            if(cur == root) { root = cur.left; }

            //2. cur不是root,是parent.left -》 则parent.left = cur.left
            if(cur == parent.left) { parent.left = cur.left; }

            //3.cur 不是root,是parent.right -》 则parent.left = cur.left
            if(cur == parent.right) { parent.right = cur.left; }

    //以上讨论的是一边为空 一边不为空的情况(包含两边都为空)

        }else { //大前提3：root 的两边都不为空 !!! --> 01:33:01 讲解  难点! --》在此会使用 替换删除 的方式进行删除。
                //
                //替换删除时 如果在cur的右边找到其右树的最小值 如果能找到 那么最小值节点的左树一定为空 不能确定右树
                //         如果在cur的左边找到其左树的最大值 如果能找到 那么最大值节点的右树一定为空 不能确定左树

            TreeNode targetParent = cur;
            //以下代码是在cur的左边找到其左树的最大值  也可在cur的右边找到其右树的最小值
            TreeNode target = cur.right;

            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetParent.left == target) {
                //cur左树的最大值在 左叶子节点
                targetParent.left = target.right;
            }else {
                //cur左树的最大值在 右叶子节点
                targetParent.right = target.right;
            }

        }
    }

    /**
     *  二叉搜索树的中序遍历
     *  中序遍历二叉搜索树的结果一定是有序的!!
     */
    public void inorder(TreeNode root) {
        if(root == null) { return; }

        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

}
